COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Possible games
C00004 00003	Games requiring a stored vocabulary
C00014 00004	Text storage with data compression
C00021 00005	Penny matching
C00023 ENDMK
C⊗;
Possible games

1)  Conway's Life
2)  Kalah
3)  Qubic (3-dimensional Tic Tac Toe)
4)  Master-mind
5)  Nine men's Morris (Muhle, Marelle, The Mill or Merry Peg)
6)  Hex
7)  Battleship
8)  Matching pennies
9)  Scrabble
10) Sprouts
11) Backgammon
12) Chinese Checkers (so called)
13) Go Moku
14) Improved Checkers
15) Bingo
16) Parcheesi
17) Chess
18) Chess monitor
19) Go
20) Nim
21) Nicomachus

Programming strategy for games

A. Continue to develop individual cartridges with different games
B. Try to develop cartridges with several simple games in each
C) Swamp the market, as it were, with many more board games
D) Develop a wider basis of types of games
E) Exploit game types not developed by competitors
F) Try to have every game that competitors have
G) Try hard to make machine seem more intelligent

Games requiring a stored vocabulary

It would be nice to be able to have the computer act as a referee for word
games and also to allow a single player to play against the machine.   All
such games would require a stored vocabulary.

There are three basic techniques  for minimizing the storage  requirements
of such a vocabulary, 1) Hashing 2) Tree storage and 3) An exploitation of
the inherent structure of English by the use of Huffman coding techniques.

1) Hashing.  Floyd has studied the hashing technique and seems to favor it
for small machines.  However it is not  error free and it makes no use  of
any inherent order  in the  corpus.  It  is undoubtedly  superior for  the
storage of completely general vocabularies but probably not as good as the
tree method for vocabularies in which only short words are allowed.  

2) Tree storage. This  technique works best for  ordered data with a  high
degree of structure and  seems to be admirably suited for vocabularies  in
which the word  size is limited.   This scheme will  be described in  more
detail below.

3) Huffman  coding.  This  technique  probably take  too much  coding  and
decoding effort  to  be of  much  use  for small  vocabularies  and  small
machines.

here are at least three forms of tree structures that are worth considering,
differing in the way in which the different word segments in the vocabulary
are identified as to their linkage with other word segments to form words.
The choice between these methods depends very much upon hardware constraints.

If we limit ourselves to single-case letters only, we need only 5 bits to
identify a character.  We then have the choice of, 1) using the three
remaining bits per byte for linkage information, 2) allowing 6 bits per
character using 5 of these for the chararacter itself and using the
remaining single bit for linkage information and packing to make use of
the otherwise unused bits in each byte, or 3) using but 5 bits per
character,allowing for 27 actual characters and having 5 special signal
characters to specify string linkage information and again packing these
5-bit characters into the 8-bit bytes.

Packing 6-bit characters into 8-bit bytes is certainly easier than it
would be to pack 5-bit characters, but any packing at all will involve
code and the cost of this code in terms of space and time will have to be
weighed against the saving in vocabulary space.

What follows is a brief description of first of these three methods.  At
the moment this seems rather well suited to our needs, that is, if we are
planning to store perhaps 500 to 1000 words.  To make it easy to
understand, only one specific implementation is described.  A study should
certainly be made of severial varients of this scheme before its actual
adoption.

The left  3  bits of  each  byte would  contain  a number  specifying  the
character position in  a word of  the character that  is contained in  the
last 5 bits of the byte.  In this way, only 1 byte is used to specify  the
first character  of  all  words  that  begin  with  any  given  character.
Similarly, if there are  2 or more  words with the  first 2 characters  in
common, then only one more  byte is used to  specify the second letter  of
these words.   The  same economy  in  bytes continues  for  all  character
positions in the words.

Unfortunately, one could not  store the characters in  the form needed  to
display them, as this requires 6 bits, but a 27-byte table would take care
of the conversion if only letters were to be allowed.

In the example shown below, the average  number of bytes per word is  2.1.
This number depends upon the character  of the vocabulary, and it is  less
if multiple endings are  shown for all root  words.  One could,  never-the
less, store a vocabulary of close to 1000 words in 2 K and perhaps write a
simple word game in 4 K of ROM.   Of course, 1000 words is a pretty  small
vocabulary and one would like to have a good many more words.

Perhaps a better compromise would be to plan on 8 K of ROM and then to use
6 K of  this for a  vocabulary of 3000  words, still leaving  2 K for  the
program.  One would still  have to limit the  allowed length of the  words
that could be  used to 8  characters in order  to be able  to specify  the
character position in 3 bits.

A sample 5-character-word  vocabulary excerpt is  shown below.  Note  that
the numbering could start with 0, thus allowing 8 letter words.  Also some
economy in  searching the  vocabulary may  be achieved  by storing  it  in
reverse word order,  and by using  the last 3  bits of each  byte for  the
number rather than the first 3 as shown.

    Characters (shown staggered)	    Word #   Total bits

1A	2B	3A	4-			1	4	
			4C	5K		2	6	
			4F	5T		3	8	
			4C	5E		4	10	
			4S	5H		5	12	
			4T	5E		6	14	
		3B	4Y			7	16	
			4O	5T		8	18	
		3E	4D			9	20	
			4T 			10	21	
		3H	4O	5R		11	24
		3I	4D	5E		12	27	
		3L	4E			13	29	
			4Y			14	30
		3O	4D	5E		15	33	
			4R	5T		16	35	
			4U	5T		17	37
			4V	5E		18	39	
		3U	4S	5E		19	42	
			4T	5-		20	44	
				5S		21	45	
	2C	3E	4-			22	48	
			4S	5-		23	50
		3H	4E	5-		24	53	
				5S		25	54
		3I	4D	5-		26	57	
				5S		27	58	
		3N	4E	5-		28	61	
				5S		29	62
		3O	4C	5K		30	63	
			4R	5N		31	65	
		3R	4E	5-		32	68	
				5S		33	69
			4I	5D		34	71	
		3T	4-			35	73
			4O	5R		36	75	
			4S			37	76	
	2D	3A	4G	5E		38	80	
			4P	5T		39	82	
		3D	4-			40	84	
			4A	5X		41	86	
			4E	5R		42	88	
			4L	5E		43	90	
			4S			44	91	
		3E	4P	5T		45	94
		3I	4T	5-		46	97	
		3M	4I	5T		47	100	
		3O	4-			48	102	
			4B	5E		49	104	
			4P	5T		50	106	
			4R	5E		51	108	
				5N		52	109	
		3U	4L	5T		53	112	
			4S	5T		54	114

Average	number	of	bytes	per	word	2.1

10,000 word vocabulary on SLOVAR [S,LES]
Text storage with data compression

Text storage in the Video-Brain can present a problem.  The size of
the available memory will usually be too small to permit the storage of the
desired amount of text without some sort of compression while the amount
of text to be stored is still too small to justify a very complicated text
compression scheme which would require an elaborate decoding program.

Some saving in space with ordinary text can be achieved without resorting
to a very complicated code if one is willing to forgo the use of upper and
lower case and if one limits the number of characters that are to be
stored..  One such code as discribed below will result in the storing of
approximately 1.7 characters per byte as compared with 1,33 for a packed
6-bit code. One would have to make a detailed study of the relative size of
the program required to use this scheme as compared to the size of the program
to do simple packing before one could be sure that this saving would be worth
while.

We will assume that one wants to use 26 letters, the digits 0 through 9
and 3 punctuation marks,  , . and ? and that we want the code to consist
of 4-bit "nibbles" which can be packed two to a byte.  It is assumed that 
there would be no need for a carriage return signal and that this function
would be handled automatically by padding with spaces to the end of a fixed
length line.

There would be three modes, a normal-letter mode, a temporary
alternate-letter mode, and a digit mode, with certain nibbles while in the
normal-letter mode and in the digit mode reserved as mode changing
signals.  The scheme as outlined could be extended to provide for yet
another mode, probably a temporary mode to allow for the inclusion of 16
additional but seldom used characters, if this seemed desirable.

When in the normal-letter mode, nibble 0 would stand for a space, nibbles
1 thru 13 would stand for the 13 most commonly used letters, with nibbles
of 14 and 15 reserved for mode changing signals.  Nibble 14 would result in
a temporary one-character change to the alternate-letter mode, with the
mode then reverting to the normal-letter mode.  Nibble 15 would result in
a change to the digit mode for all following nibbles.

When in the alternate-letter mode the nibbles 0 thru 12 would represent
the remaining letters with 13 thru 15 standing for the 3 punctuation
marks.  This mode would persist for only one character and the mode would
then revert to one of the other modes as determined by the signal that
called this temporary mode.

When in the digit mode, the nibbles 0 thru 9 would represent the digits 0
thru 9 with nibble 10 standing for a period or decimal mark.  These
nibbles would not result in any change from the digit mode.  Nibble 11
would cause a temporary change to the normal-letter mode, nibble 12 would
indicate a switch to the normal-letter mode, nibble 13 would indicate a
temporary shift to the alternate-letter mode with a return to the digit
mode, while nibble 14 would indicate a temporary shift to the
alternate-letter mode for one character and a mode change thereafter to
the normal-letter mode.  Nibble 15 is unassigned but it could be used to
invoke yet another temporary mode that could contain 16 desired but seldom
used characters.

Alternate scheme

Modified Huffman
Use a basic 4-bit code with 0 for a space, 15 for a continuation signal,
and 1 thru 14 for the most frequently used letters.  On this basis, and
using the below frequencies, 87.08% of the letters (and the space) would
each require 4 bits.  For alphabetical texts only and with no numbers or
punctuation, the rest of the letters would then require 8 bits.
This computes to an average of 4.4 bits per character (assuming 1/5
spaces).

Punctuation and the digits could be accomodated by yet another signal
signal.  This would raise the average number of bits slightly, perhaps to
4.6.

The net saving by all of this would hardly seem worth while except that the
unpacking would probably be simplier to accomplish than it would be using
a straight 5 or 6 bit code.


DON's figures
On a scale of 10000, the combined books tallied
A:815	E:1295	I:647	M:233	Q:9	U:274	Y:193
B:144	F:198	J:10	N:696	R:537	V:85	Z:3
C:200	G:216	K:93	O:740	S:570	W:279
D:515	H:772	L:405	P:130	T:930	X:11

Descending frequency: E T A H O N I S R D L W U M G C F Y B P K V X J Q Z
Penny matching

It is possible  to write a  simple program which  will usually out-play  a
person who choses heads  or tails and then  lets the program "guess"  what
his choice had been.  For the scheme to work the result of each trial must
be reported to the program correctly.

The only way that a person could hope to fool the program would be for him
to actually flip a coin or use some other random device to make his choice
for him and then, of course, he would fool the program only half the  time.
Most people refuse to  believe that a computer  program can be this  smart
and they feel intuitively that their  chances are better if they make  the
decisions. The program  would exploit  this feeling and  would detect  the
basic pattern in the player's sequence of choices.